package dp;

import java.util.ArrayList;
import java.util.List;

public class FlatCut {

    /**
     * Ширина и высота полотна
     */
    private final int W, H;

    /**
     * Список ширин, длин и цен деталей
     */
    private final List<Integer> w, h, v;
    /**
     * Количество деталей
     */
    private final int m;

    /**
     * Дискретные перестановки деталей по длине и ширине
     */
    private final List<Integer> p, q;

    private final int[][] V, item, position;
    private final char[][] guillotine;

    public FlatCut(int W, int H, List<Integer> w, List<Integer> h,
	    List<Integer> v) {
	if (W <= 0 || H <= 0 || w == null || h == null || v == null
		|| w.isEmpty() || w.size() != h.size() || w.size() != v.size()) {
	    throw new IllegalArgumentException();
	}
	this.W = W;
	this.H = H;
	this.w = w;
	this.h = h;
	this.v = v;
	this.m = v.size();
	p = new DDP(W, w).generatePoints();
	q = new DDP(H, h).generatePoints();
	V = new int[p.size()][q.size()];
	item = new int[p.size()][q.size()];
	position = new int[p.size()][q.size()];
	guillotine = new char[p.size()][q.size()];
    }

    public int V(int x, int y) {
	return V[x - 1][y - 1];
    }

    public void V(int x, int y, int value) {
	V[x - 1][y - 1] = value;
    }

    public int item(int x, int y) {
	return item[x - 1][y - 1];
    }

    public void item(int x, int y, int value) {
	item[x - 1][y - 1] = value;
    }

    public char guillotine(int x, int y) {
	return guillotine[x - 1][y - 1];
    }

    public void guillotine(int x, int y, char value) {
	guillotine[x - 1][y - 1] = value;
    }

    public int position(int x, int y) {
	return position[x - 1][y - 1];
    }

    public void position(int x, int y, int value) {
	position[x - 1][y - 1] = value;
    }

    public int w(int k) {
	return w.get(k - 1);
    }

    public int h(int k) {
	return h.get(k - 1);
    }

    public int v(int k) {
	return v.get(k - 1);
    }

    public int p(int k) {
	return p.get(k - 1);
    }

    public int q(int k) {
	return q.get(k - 1);
    }

    ValueGetter COST_GETTER = new ValueGetter() {
	@Override
	public int get(int k) {
	    return v(k);
	}
    };

    ValueGetter K_GETTER = new ValueGetter() {
	@Override
	public int get(int k) {
	    return k;
	}
    };

    public void evaluate() {
	initialize();
	for (int i = 1; i <= p.size(); ++i) {
	    for (int j = 1; j <= q.size(); ++j) {
		calcXDemention(i, j);
		calcYDemention(i, j);
	    }
	}
    }

    private void calcYDemention(int i, int j) {
	final int qj = q(j);
	final double halfOfQi = Math.ceil(qj / 2);
	int n = max(j, K_GETTER, new Condition() {
	    @Override
	    public boolean accept(int k) {
		return q(k) <= halfOfQi;
	    }

	});
	for (int y = 1; y <= n; ++y) {
	    final int qy = q(y);
	    int t = max(q.size(), K_GETTER, new Condition() {
		@Override
		public boolean accept(int k) {
		    return q(k) <= qj - qy;
		}
	    });
	    if (V(i, j) < (V(i, y) + V(i, t))) {
		V(i, j, (V(i, y) + V(i, t)));
		position(i, j, qy);
		guillotine(i, j, 'H');
	    }
	}
    }

    private void calcXDemention(int i, int j) {
	final int pi = p(i);
	final double halfOfPi = Math.ceil(pi / 2);
	int n = max(i, K_GETTER, new Condition() {
	    @Override
	    public boolean accept(int k) {
		return p(k) <= halfOfPi;
	    }

	});
	for (int x = 1; x <= n; ++x) {
	    final int px = p(x);
	    int t = max(p.size(), K_GETTER, new Condition() {
		@Override
		public boolean accept(int k) {
		    return p(k) <= pi - px;
		}
	    });
	    if (V(i, j) < (V(x, j) + V(t, j))) {
		V(i, j, (V(x, j) + V(t, j)));
		position(i, j, px);
		guillotine(i, j, 'V');
	    }
	}
    }

    private void initialize() {
	for (int i = 1; i <= p.size(); ++i) {
	    for (int j = 1; j <= q.size(); ++j) {
		final Integer pi = p(i);
		final Integer qj = q(j);
		Condition DEMENTION_CONDITION = new Condition() {
		    @Override
		    public boolean accept(int k) {
			return w(k) <= pi && h(k) <= qj;
		    }
		};
		V(i, j, max(m, COST_GETTER, DEMENTION_CONDITION));
		final int Vij = V(i, j);
		item(i, j,
			max(m, K_GETTER, DEMENTION_CONDITION, new Condition() {
			    @Override
			    public boolean accept(int k) {
				return v(k) == Vij;
			    }
			}));
		guillotine(i, j, 'X');
	    }
	}
    }

    private int max(int to, ValueGetter getter, Condition... conditions) {
	int max = 0;
	for (int k = 1; k <= to; ++k) {
	    if (isAcceptConditions(k, conditions)) {
		int value = getter.get(k);
		if (value > max) {
		    max = value;
		}
	    }
	}
	return max;
    }

    private boolean isAcceptConditions(int k, Condition... conditions) {
	for (Condition condition : conditions) {
	    if (!condition.accept(k)) {
		return false;
	    }
	}
	return true;
    }

    private interface ValueGetter {
	int get(int k);
    }

    private interface Condition {
	boolean accept(int k);
    }

    @Override
    public String toString() {
	StringBuilder builder = new StringBuilder();
//	builder.append("FlatCut2 [W=");
//	builder.append(this.W);
//	builder.append(", H=");
//	builder.append(this.H);
//	builder.append(", w=");
//	builder.append(this.w);
//	builder.append(", h=");
//	builder.append(this.h);
//	builder.append(", v=");
//	builder.append(this.v);
//	builder.append(", p=");
//	builder.append(this.p);
//	builder.append(", q=");
//	builder.append(this.q);
	builder.append("V=");
	builder.append(arrToString(this.V));
	builder.append(", \n\nitem=");
	builder.append(arrToString(this.item));
//	builder.append(", \n\nguillotine=");
//	builder.append(arrToString(this.guillotine));
//	builder.append("]");
//	builder.append(", \n\nposition=");
//	builder.append(arrToString(this.position));
//	builder.append("]");
	return builder.toString();
    }

    private String arrToString(int[][] arr) {
	StringBuilder sb = new StringBuilder();
	sb.append("[");
	for (int[] objects : arr) {
	    sb.append("\n[");
	    for (int object : objects) {
		sb.append(object + ", ");
	    }
	    sb.append("]");
	}
	sb.append("]");
	return sb.toString();
    }

    private String arrToString(char[][] arr) {
	StringBuilder sb = new StringBuilder();
	sb.append("[");
	for (char[] objects : arr) {
	    sb.append("\n[");
	    for (char object : objects) {
		sb.append(object + ", ");
	    }
	    sb.append("]");
	}
	sb.append("]");
	return sb.toString();
    }
}
